package 代码随想2._4字符串;

/**
 * @author XXX
 * @date 2024-01-16 22:30
 */

/**
 * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
 */
public class _6实现strStr {
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        if (m==0)
            return 0;
        int n = haystack.length();
        if(n<m)
            return -1;

        int i = 0;
        int j = 0;
        while (i< n-m+1){
            while (i<n && haystack.charAt(i) != needle.charAt(j))//找到首字母相等
                i++;
            if (i == n) // 没有首字母相等的
                return -1;

            // 遍历后续字符，判断是否相等
            i++;
            j++;
            while (i<n && j<m && haystack.charAt(i)==needle.charAt(j)){
                i++;
                j++;
            }
            if(j==m)//找到
                return i-j;
            else {//未找到
                i-= j -1;
                j=0;
            }
        }
        return -1;
    }

    //KMP
    public int strStr2(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next,needle);

        int j = 0;
        for (int i=0; i<haystack.length(); i++){
            while (j>0 && needle.charAt(j)!=haystack.charAt(i))
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i))
                j++;
            if (j == needle.length())
                return i-needle.length() + 1;
        }
        return -1;
    }

    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i=1; i<s.length(); i++){
            while (j>0 && s.charAt(j)!=s.charAt(i))
                j = next[j-1];
            if (s.charAt(j) == s.charAt(i))
                j++;
            next[i] = j;
        }
    }
}
